package com.company;

/**
 * @author zhf
 * @date 2021/10/14
 */

/**
 * 删除链表倒数第N个节点
 *
 * 扫描链表两遍
 * 第一遍计算出链表的长度，第二遍删除相应的节点；
 *
 *
 */


public class deleteNode {
    public class ListNode{
        int val;
        ListNode next;
        ListNode(){}  //构造函数
        ListNode(int val){
            this.val = val;
        };
        ListNode(int val,ListNode next){
            this.val = val;
            this.next = next;
        }
    }

    public static void main(String[] args) {
        deleteNode node = new deleteNode();
        node.addNode(5);
        node.addNode(4);
        node.addNode(3);
        node.addNode(2);
        node.addNode(1);


//        ListNode ans = node.removeNthFromEnd(node,4);
    }


    //头插法创建链表；
    public void addNode(int data){
        ListNode first = new ListNode();
        ListNode s = new ListNode(data);
        s.next = first.next;
        first.next = s;
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode p1 = new ListNode(0,head);//指向头结点的指针；
        int length = getlength(head);  //获取链表长度；
        ListNode p2 = p1;
        for (int i = 1; i < length-n+1; i++) {
            p2 = p2.next;
        }
        p2.next = p2.next.next;  //删除第n个节点；
        ListNode ans = p1.next;

        return ans;
    }

    //求链表长度
    public int getlength(ListNode head){
        int length = 0;
        while (head != null){
            ++length;
            head = head.next;
        }
        return length;
    }
}
